Systems that perform cryptography typically require random or pseudo-random values for generating keys and for encrypting and decrypting data, among other things. Often, these random or pseudo-random values are generated based on random or pseudo-random bits produced by hardware- or software-implemented random bit generators (also referred to as random number generators). For example, one type of random bit generator, referred to as a non-deterministic random bit generator (NRBG), produces bits non-deterministically, where every bit output by the NRBG is based on an unpredictable physical process. When properly functioning, an NRBG produces bits that are considered to be Independent and Identically Distributed (IID), or truly random. Another type of random bit generator, referred to as a deterministic random bit generator (DRBG), produces output bits deterministically using a known algorithm (e.g., an algorithm specified or recommended by the National Institute of Standards and Technology (NIST), such as in NIST Special Publication 800-90 A, Recommendation for Random Number Generation Using Deterministic Random Bit Generators, January, 2012). Because the DRBG produces its output bits deterministically, its output bits are considered to be pseudo-random, rather than being IID or truly random. However, when a DRBG is properly instantiated and correctly operating, the pseudo-random bits that it produces are likely to be considered as acceptably unpredictable for most cryptographic applications.
To instantiate a DRBG, an “entropy bitstring” is first provided to the DRBG by an entropy source. Within the DRBG, the entropy bitstring is combined with other digital inputs (e.g., a nonce and/or a personalization string) to create a seed from which the DRBG creates an initial internal working state (or an “initial value”). The DRBG may then produce an indefinite number of pseudo-random output bits based on the initial internal working state. The DRBG also may initiate a counter for tracking the number of random value requests that the DRBG receives from external requesting modules (e.g., from cryptographic and/or key generation modules), and/or a counter for tracking the quantity of pseudo-random data produced by the DRBG since the instantiation was seeded (e.g., since the initial value was created). Occasionally, based on either or both of those counters, a new seed may be created from a new entropy input, and the DRBG may update the internal working state. Either way, once a seed is properly produced and an initial value is determined, the DRBG is ready to generate pseudo-random output bits for pseudo-random number generation.
To ensure that a seed used to instantiate a DRBG results in the production of acceptably unpredictable pseudo-random output bits, the source of the entropy bitstrings (the “entropy source”) is relied upon to provide bitstrings that possesses an adequate amount of entropy. Designing such an entropy source is a difficult endeavor, and various resources are available to assist designers in this regard. For example, NIST has been instrumental in providing guidance for developing and testing entropy sources that are likely to consistently produce bitstrings with sufficient entropy for use by cryptographic applications (e.g., see NIST Draft Special Publication 800-90 B, Recommendation for the Entropy Sources Used for Random Bit Generation, August, 2012).
Typically, during the entire time that an entropy source is producing entropy bitstrings, the quality of the bitstrings' entropy is continuously analyzed using various failure mode tests and statistical tests. An entropy bitstring is considered to be of sufficient quality (“sufficiently random”) when certain entropy-indicating characteristics of the analyzed bitstring meet pre-defined criteria. When the quality of an entropy bitstring is insufficient, the entropy bitstring is not provided to the DRBG. If an entropy source were consistently to produce entropy bitstrings of insufficient quality, the DRBG's seeding and re-seeding process may be stalled. As a result, system performance may suffer (e.g., by slowing or stalling the production of random numbers that are needed by consuming applications). Accordingly, entropy sources that consistently produce bitstrings of high quality are desired (e.g., entropy sources that rarely, if ever, fail entropy quality tests). However, extremely high-quality entropy sources tend to be slower than their lower-quality counterparts, and thus there is an inherent tradeoff between entropy bitstring quality and entropy bitstring production rate. With the ever present desire to increase system performance and speed, efficient and high-quality entropy sources and entropy bitstring generation methods are desired.